//=============================================================================
//     _   _                               ____                _  _          
//    | | | |  __ _  _ __   _ __   _   _  / ___|  _ __   _ __ (_)| |_   ___ 
//    | |_| | / _` || '_ \ | '_ \ | | | | \___ \ | '_ \ | '__|| || __| / _ \
//    |  _  || (_| || |_) || |_) || |_| |  ___) || |_) || |   | || |_ |  __/
//    |_| |_| \__,_|| .__/ | .__/  \__, | |____/ | .__/ |_|   |_| \__| \___|
//                  |_|    |_|     |___/         |_|                         
//
//                     HappySprite - We make sprites happy
//
// Copyright (c) 2007 by Tank Monkey Games
//
// This library is free software; you can redistribute it and/or
// modify it under the terms of the GNU Lesser General Public
// License as published by the Free Software Foundation; either
// version 2.1 of the License, or (at your option) any later version.
//
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
// Lesser General Public License for more details.
//
// You should have received a copy of the GNU Lesser General Public
// License along with this library; if not, write to the Free Software
// Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
//=============================================================================

using System;
using System.Collections.Generic;
using System.Text;

namespace HappySprite.Simulation
{
    internal class PriorityQueue<T>
    {
        IComparer<T> comparer;
        List<T> list = new List<T>();

        internal PriorityQueue()
            : this(Comparer<T>.Default)
        {
        }

        internal PriorityQueue(IComparer<T> comparer)
        {
            this.comparer = comparer;
        }

        internal void Clear()
        {
            list.Clear();
        }

        internal int Count
        {
            get { return list.Count; }
        }

        internal T Peek()
        {
            if (list.Count > 0)
                return list[0];

            return default(T);
        }

        internal int Push(T item)
        {
            int thisIndex = list.Count;
            list.Add(item);

            do
            {
                if (thisIndex == 0)
                    break;

                int otherIndex = (thisIndex - 1) / 2;

                if (comparer.Compare(list[thisIndex], list[otherIndex]) >= 0)
                    break;

                // Swap items
                T value = list[thisIndex];
                list[thisIndex] = list[otherIndex];
                list[otherIndex] = value;
                thisIndex = otherIndex;
            } 
            while (true);

            return thisIndex;
        }

        public T Pop()
        {
            T result = list[0];
            int p = 0, p1, p2, pn;
            list[0] = list[list.Count - 1];
            list.RemoveAt(list.Count - 1);

            do
            {
                pn = p;
                p1 = 2 * p + 1;
                p2 = 2 * p + 2;

                if (list.Count > p1 && comparer.Compare(list[p], list[p1]) > 0)
                    p = p1;

                if (list.Count > p2 && comparer.Compare(list[p], list[p2]) > 0)
                    p = p2;

                if (p == pn)
                    break;

                // Swap items
                T value = list[p];
                list[p] = list[pn];
                list[pn] = value;
            } 
            while (true);

            return result;
        }
    }
}
